#!/usr/bin/env python
# -*- coding:utf-8 -*-
import networkx as nx
import numpy as np
import copy
import pyexcel
np.set_printoptions(threshold=np.nan)

def G_init(file_name):
    global G
    G=nx.Graph()
    sheet = pyexcel.get_sheet(file_name=file_name)
    a = sheet.row[:]
    b = []
    for i in a:
        b.append(tuple(i))
    e=b
    G.add_edges_from(e)
    global edges
    edges = G.edges()
    global degree
    degree = G.degree()


def list_split(li,lenth_num):
    '''
    分割li
    :param li:
    :param lenth_num:分割后每个li元素的个数
    :return:按照
    '''
    new_Li = []
    while len(li) > lenth_num:
        new_Li.append(li[:lenth_num])
        for i in li[:lenth_num]:
            li.remove(i)
    new_Li.append(li)
    return new_Li


def dropnone(cp_Li):
    '''
    删除列表的空元素
    :param cp_Li: 处理前的li
    :return: 处理后的li
    '''
    for i in cp_Li:
        while None in i:
            i.remove(None)
    while [] in cp_Li:
        cp_Li.remove([])
    return cp_Li


def Q(C, G):
    '''
    计算Q值
    :param C:社区的列表
    :param G: 无向图对象
    :return:计算的Q值
    '''
    edges = G.edges()
    m = len(edges)
    DEG = G.degree()
    ret = 0.0
    for c in C:
        line = 0
        for x in c:
            for y in c:
                if x <= y:
                    if (x, y) in edges:
                        line = line + 1
                else:
                    if (y, x) in edges:
                        line = line + 1
        SUM_D = 0
        for x in c:
            SUM_D = SUM_D + DEG[x]
        tmp = line * 1.0 / (2 * m) - (SUM_D * 1.0 / (2 * m)) * (SUM_D * 1.0 / (2 * m))
        ret = ret + tmp
    return ret


def change(li):
    '''
    li的平移
    :param li: 处理前的li
    :return:处理后的li
    '''
    num = len(li)-1
    li.insert(0,li[num])
    li.pop()
    # print(li)
    return li


def move_1(li,li_num=0):
    '''
    进行li的平移变换
    :param li: 需要处理的列表
    :param li_num: 默认填0
    :return: 平移后的li
    '''
    new = []
    for k,v in enumerate(li[li_num]):
        new = copy.copy(li)
        q_old = Q(li,G)
        new[li_num+1].append(new[li_num][k])
        q_new = Q(new,G)
        if q_new>q_old:
            new[li_num][k] = None
        else:
            new[li_num + 1].pop()
        # print(new)
        dropnone(new)
    return new


def run():
    '''
    循环方法
    :return: （[这里是分组后的节点列表]，Q值）
    '''
    li = list(degree.keys())
    li = list_split(li,5)
    Befor_Q=  Q(li,G)
    STOP_Q=100
    # start = time.time()
    while STOP_Q>Befor_Q:
        Befor_Q = Q(li,G)
        for i in range(len(degree)):
            li = move_1(li,0)
            li = change(li)
            STOP_Q=Q(li,G)
    return li,STOP_Q


if __name__ == '__main__':
    G_init('IEEE33.xlsx')
    ret = run()
    print(ret)